package com.smh;

import org.junit.jupiter.api.Test;

import java.util.*;

/**
 * @author shiminghui
 * @date 2025/3/15 16:25
 * @description: TODO
 */
public class _048_图_kruskal {


    @Test
    public void test1() {
        Vertex v1 = new Vertex(0);
        Vertex v2 = new Vertex(1);
        Vertex v3 = new Vertex(2);
        Vertex v4 = new Vertex(3);
        Vertex v5 = new Vertex(4);
        Vertex v6 = new Vertex(5);


        v1.setEdges(List.of(new Edge(v1, v3, 1), new Edge(v1, v6, 1)));
        v2.setEdges(List.of(new Edge(v2, v3, 1)));
        v3.setEdges(List.of(new Edge(v3, v4, 1), new Edge(v3, v2, 1), new Edge(v3, v1, 1)));
        v4.setEdges(List.of(new Edge(v4, v5, 1), new Edge(v4, v3, 1)));
        v5.setEdges(List.of(new Edge(v5, v6, 1), new Edge(v5, v4, 1)));
        v6.setEdges(List.of(new Edge(v6, v1, 1), new Edge(v6, v5, 1)));

        kruskal(List.of(v1, v2, v3, v4, v5, v6));
    }

    public void kruskal(List<Vertex> vertexs) {
        PriorityQueue<Edge> minHeap = new PriorityQueue<>(Comparator.comparingInt(Edge::getWeight));
        for (Vertex vertex : vertexs) {
            List<Edge> edges = vertex.getEdges();
            if (edges == null) {
                continue;
            }
            for (Edge edge : edges) {
                minHeap.offer(edge);
            }
        }

        _049_并查集合.DisJointSet disJointSet = new _049_并查集合.DisJointSet(vertexs.size());
        for (int i = 0; i < vertexs.size(); i++) {
            disJointSet.set(i, i);
        }

        while (!minHeap.isEmpty()) {
            Edge edge = minHeap.poll();
            Vertex from = edge.getFrom();
            Vertex to = edge.getTo();
            if (disJointSet.find(from.getId()) != disJointSet.find(to.getId())) {
                disJointSet.union(from.getId(), to.getId());
                System.out.println(from.getId() + "-->" + to.getId() + ":" + edge.getWeight());
            }
        }
    }

    /**
     * v2-->v3:1
     * v3-->v1:1
     * v4-->v3:1
     * v5-->v6:1
     * v6-->v1:1
     */

    private class Vertex {
        private String name;
        private Integer id; // Vertex的id
        private int hash;
        private int status;
        private List<Edge> edges;
        private int inDegree; // 入度
        private boolean isVisited; // 是否访问过
        private int distance; // 到该顶点的最短路径
        private Vertex pre; // 记录该顶点的前驱顶点

        { // 初始化
            status = 0;
            distance = Integer.MAX_VALUE;
            isVisited = false;
            inDegree = 0;
        }

        public Vertex(String name) {
            this.name = name;
        }

        public Vertex(Integer id) {
            this.id = id;
        }

        public Vertex(String name, List<Edge> edges) {
            this.name = name;
            this.edges = edges;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Vertex vertex = (Vertex) o;
            return status == vertex.status && inDegree == vertex.inDegree && isVisited == vertex.isVisited && distance == vertex.distance && Objects.equals(name, vertex.name) && Objects.equals(edges, vertex.edges) && Objects.equals(pre, vertex.pre);
        }

        @Override
        public int hashCode() {
            return Objects.hash(name);
        }

        public Vertex getPre() {
            return pre;
        }

        public void setPre(Vertex pre) {
            this.pre = pre;
        }

        public boolean isVisited() {
            return isVisited;
        }

        public void setVisited(boolean visited) {
            isVisited = visited;
        }

        public int getDistance() {
            return distance;
        }

        public void setDistance(int distance) {
            this.distance = distance;
        }

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }

        public int getStatus() {
            return status;
        }

        public void setStatus(int status) {
            this.status = status;
        }

        public List<Edge> getEdges() {
            return edges;
        }

        public void setEdges(List<Edge> edges) {
            this.edges = edges;
        }

        public int getInDegree() {
            return inDegree;
        }

        public void setInDegree(int inDegree) {
            this.inDegree = inDegree;
        }

        @Override
        public String toString() {
            return "Vertex{" +
                    "name='" + name + '\'' +
                    '}';
        }

        public Integer getId() {
            return id;
        }

        public void setId(Integer id) {
            this.id = id;
        }
    }

    private class Edge {
        private Vertex from;
        private Vertex to;
        private int weight;

        public Edge(Vertex from, Vertex to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }

        public Vertex getFrom() {
            return from;
        }

        public void setFrom(Vertex from) {
            this.from = from;
        }

        public Vertex getTo() {
            return to;
        }

        public void setTo(Vertex to) {
            this.to = to;
        }

        public int getWeight() {
            return weight;
        }

        public void setWeight(int weight) {
            this.weight = weight;
        }
    }
}
